package 牛客101.链表;

import java.util.ArrayList;
import java.util.function.DoubleUnaryOperator;

public class 合并k个已排序的链表 {


    public ListNode mergeKlists(ArrayList<ListNode> lists)
    {
        if(lists.isEmpty())
        {
            return null;
        }
        // k个链表归并排序
        return divideMerge(lists,0, lists.size()-1);
    }
    public static ListNode Merge(ListNode head1,ListNode head2)
    {
        if(head1 == null)
            return head2;
        if(head2 == null)
            return head1;

        ListNode dummy = new ListNode(0), p = dummy;
        while(head1!=null && head2!=null)
        {
            if(head1.val > head2.val)
            {
                p.next = head2;
                head2 = head2.next;
            }else{
                p.next = head1;
                head1 = head1.next;
            }
            p = p.next;
        }
        dummy.next = (head1 == null)? head2:head1;
        return  dummy.next;
    }
    public ListNode divideMerge(ArrayList<ListNode> lists,int left,int right)
    {
        if(right<left)
        {
            return null;
        }
        else if(left == right)
        {
            return lists.get(left);
        }


        // 从中间进行分离
        int mid = (left+right)/2;
        return Merge(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));

    }


    public static void main(String[] args) {

    }
}
